package bintree.LeetCode;
//106. 从中序与后序遍历序列构造二叉树

/**
 * 思路：后续遍历，左右根。把后续结果翻转，就是根右左。再用中序遍历判断根的左右子树。
 */
public class Num106_buildTree {
    public int index;//用来判断走到后续数组的哪一位了
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //设计一个方法，根据后续和中序数组，还原二叉树。
        return in_after(postorder, inorder);
    }

    /**
     * 传入一个后续遍历数组和中序遍历数组，就能还原一颗二叉树
     */
    private TreeNode in_after(int[] postorder, int[] inorder) {
        //先设计一个方法，逆序后续数组。创建新的数组进行，对原数组不修改
        int[] arr = inverse(postorder);//逆序后变成，根右左
        //再设计一个方法，根据逆序的后续数组和中序数组，再根据中序数组的范围判断还原二叉树。
         return buildTreeHelper(arr, inorder, 0, inorder.length - 1);//有效元素范围
    }

    /**
     *  传入逆序的后续数组和中序，再根据中序数组的范围，就能还原一个二叉树
     */
    /**
     * 运行思路先，右，右，右到低。到底之后返回到倒数第二个右节点，连接它的左节点是否存在。
     * 如果存在就继续 右右右到低，然后看左是否存在。如果不存在或者已经处理完毕就返回到上一级。
     *  根节点的左是最后处理的。
     */
    private TreeNode buildTreeHelper(int[] postorder, int[] inorder, int left, int right) {
        //边界
        if(left > right){
            //左比右大，中间肯定没有元素了
            return null;
        }
        //终止条件
        if(index == postorder.length){
            //对后续数组的根都读取完毕，就可以结束了。
            return null;
        }
        TreeNode root = new TreeNode(postorder[index]);//创建一个新节点
        index ++;//创造一个新节点就往后走一步
        //因为需要知道该根节点在中序里面的左右子树范围，所以需要知道该节点索引
        //设计一个方法，根据val值寻找数组内对应的位置
        int pos = find(root.val,inorder);
        //因为是根右左，所以先递归右再左
        root.right = buildTreeHelper(postorder, inorder, pos + 1, right);//有效元素范围
        root.left = buildTreeHelper(postorder, inorder,  left, pos - 1);//有效元素范围

        return root;
    }

    /**
     * 寻找val值在数组中是否存在，返回其索引
     */
    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if(val == inorder[i]){
                return i;
            }
        }
        return -1;
    }

    /**
     * 传入一个数组，根据这个数组创建一个新的数组，内容是逆序
     */
    private int[] inverse(int[] postorder) {
        int[] arr = new int[postorder.length];
        int n = 0;
        for (int i = postorder.length - 1; i >= 0 ; i--, n++) {
             arr[n] = postorder[i];
        }
        return arr;
    }
}
